Maximum Twin Sum of a Linked List

LeetCode 2236 | Difficulty: Medium

Medium

Problem Description

In a linked list of size n, where n is even, the i^th node (0-indexed) of the linked list is known as the twin of the (n-1-i)^th node, if 0 <= i <= (n / 2) - 1.

- For example, if `n = 4`, then node `0` is the twin of node `3`, and node `1` is the twin of node `2`. These are the only nodes with twins for `n = 4`.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

- The number of nodes in the list is an **even** integer in the range `[2, 10^5]`.

- `1 <= Node.val <= 10^5`

Topics: Linked List, Two Pointers, Stack

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 276 ms)

Metric	Value
Runtime	276 ms
Memory	52.6 MB
Date	2022-02-02

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public int PairSum(ListNode head)
{
    ListNode slow = head, fast = head, prev = null;
    while (fast != null && fast.next != null)
    {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null;
    var temp1 = Reverse(head);
    var temp2 = slow;
    fast = temp1;
    int max = Int32.MinValue;
    while (slow != null)
    {
        max = Math.Max(max, slow.val +fast.val);
        slow = slow.next;
        fast=fast.next;
    }
    head = Reverse(head);
    prev.next = temp2;
    return max;
}

ListNode Reverse(ListNode head)
{
    ListNode rev = null, current = head;
    while(current!=null)
    {
        var next = current.next;
        current.next = rev;
        rev = current;
        current = next;     
    }
    return rev; 
}
}

📜 3 more C# submission(s)

Submission (2022-02-02) — 276 ms, 54.1 MB

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public int PairSum(ListNode head) {
        ListNode slow = head, fast = head, prev = null;
    List<int> firstHalf = new List<int>();
    while (fast != null && fast.next != null)
    {
        firstHalf.Add(slow.val);
        slow = slow.next;       
        fast = fast.next.next;
    }
    int max = Int32.MinValue;
    int i = firstHalf.Count-1;
    while(slow!=null)
    {
        max = Math.Max(max, slow.val + firstHalf[i--]);
        slow = slow.next;   
    }
    return max;
    }
}

Submission (2022-02-02) — 394 ms, 53.8 MB

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public int PairSum(ListNode head)
{
    ListNode slow = head, fast = head;
    List<int> firstHalf = new List<int>();
    while (fast != null && fast.next != null)
    {
        firstHalf.Add(slow.val);
        slow = slow.next;       
        fast = fast.next.next;
    }
    int max = Int32.MinValue;
    int i = firstHalf.Count-1;
    while(slow!=null)
    {
        max = Math.Max(max, slow.val + firstHalf[i--]);
        slow = slow.next;   
    }
    return max;
}
}

Submission (2022-02-02) — 477 ms, 56.3 MB

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public int PairSum(ListNode head)
{
    ListNode slow = head, fast = head, prev = null;
    while (fast != null && fast.next != null)
    {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null;
    fast = Reverse(head);
    //store temp to reconnect later
    var temp = slow;
    int max = Int32.MinValue;
    while (slow != null)
    {
        max = Math.Max(max, slow.val +fast.val);
        slow = slow.next;
        fast=fast.next;
    }
    head = Reverse(head);
    prev.next = temp;
    return max;
}

private ListNode Reverse(ListNode head)
{
    ListNode rev = null, current = head;
    while(current!=null)
    {
        var next = current.next;
        current.next = rev;
        rev = current;
        current = next;     
    }
    return rev; 
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Stack	$O(n)$	$O(n)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: How can "reversing" a part of the linked list help find the answer?

Hint 2: We know that the nodes of the first half are twins of nodes in the second half, so try dividing the linked list in half and reverse the second half.

Hint 3: How can two pointers be used to find every twin sum optimally?

Hint 4: Use two different pointers pointing to the first nodes of the two halves of the linked list. The second pointer will point to the first node of the reversed half, which is the (n-1-i)th node in the original linked list. By moving both pointers forward at the same time, we find all twin sums.